package hdoj;

import java.util.Scanner;

//1~n中能够整除13并且含有13子串的个数
public class DigitDpHDU3652 {

	public static void main(String[] args) {
		DigitDpHDU3652 object = new DigitDpHDU3652();
		object.getRes();
	}
	
	private void getRes() {
		Scanner scanner = new Scanner(System.in);
		int n;
		//初始化dp数组
		for(int i = 0; i < 12; i++){
			for (int j = 0; j < 10; j++) {
				for (int k = 0; k < 2; k++) {
					for (int m = 0; m < 13; m++) {
						dp[i][j][k][m] = -1;
					}
				}
			}
		}
		while(scanner.hasNext()){
			n = scanner.nextInt();
			System.out.println(solve(n));
		}
		scanner.close();
	}

	int solve(int n) {
		int len = 0;
		for (int i = 0; i < bits.length; i++) {
			bits[i] = 0;
		}
		while (n != 0) {
			bits[len++] = n % 10;
			n /= 10;
		}
		//这里传递的是length - 1, 对应的是最高位
		//所以int end = flag ? bits[length] : 9;
		// return dfs(len - 1, 0, 0, 0, true);
		return dfs(len + 1, 0, 0, 0, true);
	}
	
	//dp[i][j][k][m]表示i位数，最高位固定为j,是否有包含13的(k = 1有，0没有)模13余数是m的个数
	
	//if(k == 1)
	//dp[i][j][k][m] =  dp[i - 1][x][1][ (m - x * (10)) % 13](x枚举i-1位从 0~9)
	// if j == 3 && x == 1   dp[i][j][k][m] = dp[i][j][k][m] + 
	//                                        dp[i - 1][x][0][ (m - x * (10)) % 13]
	
	//if(k == 0)	//不包括13
	// if(! (j == 3 && x == 1))
	//dp[i][j][k][m] = dp[i - 1][x][0][ (m - x * (10)) % 13]
	
	int[][][][] dp = new int[12][10][2][13];
	int[] bits = new int[10];
	
	
	//dfs返回的结果表示的dp[length][now][k][mod]
	public int dfs(int length, int mod, int k, int now, boolean flag){
		//其实这个就是初始化条件
		//我们要判断的是是否取余等于0并且k == 1
		//比如13
		if (length <= 1){
			return mod == 0 && k == 1 ? 1 : 0;
		}
//		if(length == 1){
//			return mod == 0 && k == 1 ? 1 : 0;
//		}
		if(!flag && dp[length][now][k][mod] != -1){
			return dp[length][now][k][mod];
		}
		int end = flag ? bits[length - 2] : 9;
		int ans = 0;
		//模板写法
		for (int i = 0; i <= end; i++) {
			ans += dfs(length - 1, (mod * 10 + i) % 13, k == 1 || (now == 1 && i == 3) ? 1 : 0,
					i, flag && (i == end));
			// System.out.println("length: " + length + " ans: " + ans);
		}
		if (!flag){
			dp[length][now][k][mod] = ans;
		}
		return ans;
	}
}
